#include <iostream>
#include <ctime>
using namespace std;
const int maxsize=100;
int n;
int a[maxsize];
void init(int a[],int n)
{

    srand(time(0));
    for(int i=1;i<=n;++i)
    {
        a[i]=rand()%100;
    }
}
void print(int a[],int n)
{
    for(int i=1;i<=n;++i)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
//从x结点向下调整到len为止
void AdjustDown(int x,int len)
{
    for(int i=2*x;i<=len;i*=2)
    {
        //找出x 左右孩子最大的一个
        if(i+1<=len&&a[i+1]>a[i])
        {
            i++;
        }
        //此时i已经指向最大的哪一个
        //调整大根堆 如果孩子大 父结点下调并且继续判断是否满足大根堆性质
        if(a[x]<a[i])
        {
            swap(a[x],a[i]);
            x=i;//下次再循环  就要从x的孩子出发
        }
    }
}
//从最后一个非叶结点开始调整
void CreateBigHeap()
{
    for (int i = n/2; i>=1; --i) {
           AdjustDown(i,n);
    }
}

void HeapSort()
{
    //先调整大根堆
    //不断循环 把第一个和最后一个交换 最大的沉到最底下 再调整堆顶
    CreateBigHeap();
    for(int i=n;i>=2;--i)
    {
        swap(a[i],a[1]);//每次都和第一个进行交换
        AdjustDown(1,i-1);
    }
}
int main() {
    cin>>n;
    init(a,n);
    print(a,n);
    HeapSort();
    print(a,n);




    return 0;
}
